public class 绝对差不超过限制的最长连续子数组 {

    public static int MAXN = 100001;
    public static int[] dequeMin = new int[MAXN]; // 存储的其实是下标
    public static int[] dequeMax = new int[MAXN]; // 存储的其实是下标
    public static int hMin,tMax,hMax,tMin,ans;
    public static int longestSubarray(int[] nums, int limit) {
        hMin = hMax = tMax = tMin = 0;
        int n = nums.length;
        // 将元素都添加到队列中
        int l = 0;
        ans = 0;
        // 随着长度增加, 只会使 最大值增加或最小值减小, 导致 limit 变大, 当 limt 大的时候, 就开始收缩
        for (int r = 0; r < n; r++) {
            // 维护单调队列的最大值的元素
            while (hMax < tMax && nums[dequeMax[tMax - 1]] <= nums[r]) {
                tMax--;
            }
            dequeMax[tMax++] = r;
            // 维护最小的元素
            while (hMin < tMin && nums[dequeMin[tMin - 1]] > nums[r]) {
                tMin--;
            }
            dequeMin[tMin++] = r;
            while (hMax < tMax && hMin < tMin && nums[dequeMax[hMax]] - nums[dequeMin[hMin]] > limit) {
                if (dequeMin[hMin] == l) {
                    hMin++;
                }
                if (dequeMax[hMax] == l) {
                    hMax++;
                }
                l++;
            }
            ans = Math.max(ans,r - l + 1);
        }
        return ans;
    }
}
